//
// Created by isabella on 25-5-28.
//
#include <common.h>
#include <format>
#include <json.hpp>

class Solution {
    string text;
    string pattern;

public:
    vector<int> next;

    Solution(string s, string p) {
        text = s;
        pattern = p;
        next.resize(p.length());
        getKMP();
    }

    int find() {
        int j = 0;
        for (int i = 0; i < text.length(); i++) {
            while (j > 0 && text[i] != pattern[j]) {
                j = next[j - 1];
            }
            if (text[i] == pattern[j]) {
                j++;
            }
            if (j == pattern.length()) {
                return i - pattern.length() + 1;
            }
        }
        return -1;
    }

    void getKMP() {
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < pattern.length(); i++) {
            while (j > 0 && pattern[i] != pattern[j]) {
                j = next[j - 1];
            }
            if (pattern[i] == pattern[j]) {
                j++;
            }
            next[i] = j;
        }
    }
};

int main() {
    class Obj {
    public:
        string s;
        string p;

        Obj() = default;

        Obj(string s, string p): s(std::move(s)), p(std::move(p)) {
        }
    };

    unordered_map<int, Obj> mp;


    mp[0] = Obj{"ggoogoogogoogle", "google"};
    mp[1] = Obj{"aabbaababc", "ababc"};
    mp[2] = Obj{"aabbabaababaa", "ababaa"};
    mp[3] = Obj{"aaaaaaaaab", "aaaab"};
    Obj fill = mp[3];


    auto sp = new Solution(fill.s, fill.p);
    int find = sp->find();
    cout << find << endl;
    nlohmann::json j;
    vector<string> chart;
    for(char & i : fill.p) {
        chart.emplace_back(std::format("{}",i));
    }
    j["pattern"] = chart;
    vector<string > num;

    for(auto i : sp->next) {
        num.emplace_back(std::format("{}",i));
    }
    j["next"] = num;
    cout << "pattern:" << j["pattern"] << endl;
    cout << "next   :" << j["next"] << endl;
    delete sp;
    return 0;
}
